package q791_customSortString;

public class Solution_2 {
    /*
    计数排序
    首先遍历字符串 s，使用数组或哈希表统计每个字符出现的次数。
    随后遍历字符串 order 中的每个字符 c，
    如果其在 s 中出现了 k 次，就在答案的末尾添加 k 个 c，并将数组或哈希表中对应的次数置为 0。
    最后我们遍历一次哈希表，对于所有次数 k 非 0 的键值对 (c, k)，在答案的末尾添加 k 个 c 即可。
     */
    public String customSortString(String order, String s) {
        int[] freq = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            ++freq[ch - 'a'];
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < order.length(); ++i) {
            char ch = order.charAt(i);
            while (freq[ch - 'a'] > 0) {
                ans.append(ch);
                freq[ch - 'a']--;
            }
        }
        for (int i = 0; i < 26; ++i) {
            while (freq[i] > 0) {
                ans.append((char) (i + 'a'));
                freq[i]--;
            }
        }
        return ans.toString();
    }
}
